home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
HPAVC
/
HPAVC CD-ROM.iso
/
WD_SRC.ZIP
/
BSP_GEN
/
BSP_GEN.CPP
next >
Wrap
C/C++ Source or Header
|
1995-01-12
|
18KB
|
646 lines
#include "..\Source\LastWolf.hpp"
// ERASE THIS.
Fixed hello;
// The list of Lines and Points.
CLineArray *pLines;
CPointArray *pPoints;
WORD nOriginalPoints, nOriginalLines;
// Global variable .. tells how many Lines were split.
DWORD nSplits=0;
// How many times it's chosen the most balanced Line over the least splits.
DWORD nBalancesChosen=1, nSplitsChosen=1;
// The percentage the program should try to maintain for choosing balance over splits.
DWORD balanceImportance;
// How many times a line was split exactly along another line.
WORD nExactIntersections=0;
// Used for best split calculations .. incremented each time the tree is split.
WORD nSplitTrees=0;
// Makes BestSplit() use the best balance a certain amount of times.. Helps
// to ensure that the top levels of the tree are as balanced as possible.
WORD forceBalance=5;
CLine *GenerateBspTree(BspCommandLine *pCommandLine, CLineArray *pLinesToFill, CPointArray *pPointsToFill)
{
CLine *pRootNode;
WORD i;
pLines = pLinesToFill;
pPoints = pPointsToFill;
dr_InitTables();
if( pCommandLine->bDoomLevel )
printf("\nLoading WAD file %s..\n", pCommandLine->pFilename);
else
printf("\nLoading text file %s..\n", pCommandLine->pFilename);
if( pCommandLine->bDoomLevel )
{
if( !LoadDoomLevel( pCommandLine->pFilename, pCommandLine->pLevelName, pLines, pPoints, pCommandLine->bLoadDoomTextures, pCommandLine->pTextureWadName ) )
{
printf("Error loading WAD %s, level %d.\n\n", pCommandLine->pFilename, pCommandLine->pLevelName );
return NULL;
}
}
else
{
if( !LoadTextData( pCommandLine->pFilename, pLines, pPoints) )
{
printf("\nCouldn't load the data!");
return NULL;
}
}
puts("");
puts("Creating BSP tree...");
balanceImportance = FIX(pCommandLine->balance) / 100;
nOriginalPoints = pPoints->NumElements();
nOriginalLines = pLines->NumElements();
// Just give all the Lines random wall colors.
for( i=0; i < pLines->NumElements(); i++ )
pLines->GetLine(i)->wallColor = rand() % 255;
// Generate the tree. After this function call, pLeft and pRight should
// be filled in on all the Lines (there will be some new Lines added to pLines too).
// Now just store them.
pRootNode = GenerateSubTree( pLines );
PrecalculateData( pLines );
puts("Checking BSP tree integrity ... ");
if( !CheckTreeValidity() )
puts("Check failed!\n");
else
puts("Check passed!\n");
// Write the data to the output file.
printf("Writing data to %s.\n", pCommandLine->pOutputFile);
OutputTextData( pRootNode, pCommandLine->pOutputFile, pLines, pPoints );
// If there's an extra argument, graphically display the data.
#ifdef DISPLAY_GRAPHICAL
if( pCommandLine->bGraphicalDisplay )
{
printf("Displaying graphics...");
DisplayGraphicalData(pLines, pPoints);
}
#endif
printf("\nDone!\n\n");
return pRootNode;
}
CLine *GenerateSubTree( CLineArray *pTreeLines )
{
CLineArray pLeftSide, pRightSide;
CLine *pRootLine;
// The terminal condition..
if( pTreeLines->NumElements() == 0 )
return NULL;
else if( pTreeLines->NumElements() == 1 )
return pTreeLines->GetLine(0);
// Split the tree.
pRootLine = Split_Tree( pTreeLines, &pLeftSide, &pRightSide );
pRootLine->pLeft = GenerateSubTree( &pLeftSide );
pRootLine->pRight = GenerateSubTree( &pRightSide );
return pRootLine;
}
CLine *Split_Tree( CLineArray *pLineList, CLineArray *pLeftList, CLineArray *pRightList )
{
CLine *pSplit;
// These two are only used if a Line is split.
CLine *pNewLeft, *pNewRight;
CLine *pCurLine;
Index curLine;
SideDir testSide;
WORD nElements;
WORD nLeft, nRight, nSplit;
WORD curLeft=0, curRight=0, curSplit=0;
// Just update this global variable.
++nSplitTrees;
// Get the best split out of the array.
pSplit = BestSplit( pLineList, &nLeft, &nRight, &nSplit );
// Set the sizes of the arrays ahead of time instead of appending every line to save MUCH time.
pLeftList->SetSize( (UWORD)(nLeft+nSplit) );
pRightList->SetSize( (UWORD)(nRight+nSplit) );
// Use a variable for the for loop because pLineList might get some elements added to it.
nElements = pLineList->NumElements();
for( curLine=0; curLine < nElements; curLine++ )
{
pCurLine = pLineList->GetLine(curLine);
// Don't do anything to the Line you split everything by.
if( pCurLine == pSplit )
continue;
// See which side this Line is on.
testSide = LineSide( pSplit, pCurLine );
switch( testSide )
{
case LeftSide:
pLeftList->Set( curLeft, pCurLine );
++curLeft;
break;
case RightSide:
pRightList->Set( curRight, pCurLine );
++curRight;
break;
case Intersect:
++nSplits;
SplitLine( pSplit, pCurLine, &pNewLeft, &pNewRight );
pLeftList->Set( curLeft, pNewLeft );
pRightList->Set( curRight, pNewRight );
++curLeft;
++curRight;
break;
}
}
return pSplit;
}
CLine *BestSplit( CLineArray *pLineList, WORD *pNLeft, WORD *pNRight, WORD *pNSplits )
{
WORD curSplitLine, curLine;
// The two types of tests that can be done.
// After finding the best of each, it makes a decision based on
// the importance of having each type.
WORD bestNumSplits=32000, bestSplitIndex=0;
WORD bestBalance=32000, bestBalanceIndex=0;
WORD nTestSplits, nLeft, nRight;
WORD bestLeft, bestRight, bestSplit;
WORD LeftRightDiff;
CLine *pCurLine;
SideDir testSide;
// This starts numTestLines with a high value and brings it down gradually.
// It's very important that near the root node the tree is very balanced.
// This ensures that it is.
WORD numTestLines = (WORD)(35 - nSplitTrees);
if( numTestLines < 7 )
numTestLines = 7;
if( numTestLines > pLineList->NumElements() )
numTestLines = pLineList->NumElements();
// Tells if it's looking for the best balance or the least splits.
BOOL bGoForBalance;
if( forceBalance > 0 )
{
bGoForBalance = TRUE;
++nBalancesChosen;
--forceBalance;
}
else
{
// ERASE THIS.
hello = FDiv(FIX(nSplitsChosen), FIX(nBalancesChosen));
if( FDiv(FIX(nSplitsChosen), FIX(nBalancesChosen)) < (FIXED_ONE - balanceImportance) )
{
bGoForBalance = FALSE;
++nSplitsChosen;
}
else
{
bGoForBalance = TRUE;
++nBalancesChosen;
}
}
for( curSplitLine=0; curSplitLine < numTestLines; curSplitLine++ )
{
pCurLine = pLineList->GetLine(curSplitLine);
nTestSplits=nLeft=nRight=0;
for( curLine=0; curLine < pLineList->NumElements(); curLine++ )
{
// Test every Line in the array for the number of splits.
if( curLine == curSplitLine )
continue;
testSide = LineSide( pCurLine, pLineList->GetLine(curLine) );
switch( testSide )
{
case LeftSide:
++nLeft;
break;
case RightSide:
++nRight;
break;
case Intersect:
++nTestSplits;
break;
}
}
if( bGoForBalance )
{
LeftRightDiff = (WORD)DIFF(nLeft,nRight);
// Only do the best balance.
if( LeftRightDiff < bestBalance )
{
bestBalance = LeftRightDiff;
bestNumSplits = nTestSplits;
bestBalanceIndex = curSplitLine;
bestLeft = nLeft;
bestRight = nRight;
bestSplit = nTestSplits;
}
// This is an extra test here. If the balances are the same, it gets the one
// with the least number of splits too.
else if( LeftRightDiff == bestBalance )
{
if( nTestSplits < bestNumSplits )
{
bestBalanceIndex = curSplitLine;
bestNumSplits = nTestSplits;
bestLeft = nLeft;
bestRight = nRight;
bestSplit = nTestSplits;
}
}
}
else
{
// Only do the least number of splits.
if( nTestSplits < bestNumSplits )
{
bestNumSplits = nTestSplits;
bestSplitIndex = curSplitLine;
bestLeft = nLeft;
bestRight = nRight;
bestSplit = nTestSplits;
}
}
}
*pNLeft = bestLeft;
*pNRight = bestRight;
*pNSplits = bestSplit;
if( bGoForBalance )
return pLineList->GetLine(bestBalanceIndex);
else
return pLineList->GetLine(bestSplitIndex);
}
SideDir LineSide( CLine *pMainLine, CLine *pTestLine )
{
// Get the angle for pMainLine.
// Rotate both the Lines by pMainLine's angle.
// Parametrically clip pToSplit against the X axis.
Angle angMain;
Fixed y1, y2, mainY;
BOOL bSharePoint=FALSE;
WORD testSharePoint;
if( pMainLine->pPoint1 == pTestLine->pPoint1 || pMainLine->pPoint2 == pTestLine->pPoint1 )
{
bSharePoint = TRUE;
testSharePoint = 1;
}
else if( pMainLine->pPoint1 == pTestLine->pPoint2 || pMainLine->pPoint2 == pTestLine->pPoint2 )
{
bSharePoint = TRUE;
testSharePoint = 2;
}
angMain = GetAngle( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
pMainLine->pPoint2->localX, pMainLine->pPoint2->localY );
angMain = (ANGLE_RES - angMain) & ANGLE_MASK;
// Rotate all of pToSplit's vertices *around* pMainLine's first Point.
RotatePointYOnly( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
angMain, pTestLine->pPoint1->localX, pTestLine->pPoint1->localY,
&y1 );
RotatePointYOnly( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
angMain, pTestLine->pPoint2->localX, pTestLine->pPoint2->localY,
&y2 );
mainY = FIX(pMainLine->pPoint1->localY);
if( bSharePoint )
{
if( testSharePoint == 1 )
{
if( y2 < mainY )
return RightSide;
else if( y2 > mainY )
return LeftSide;
else
return Intersect;
}
else
{
if( y1 < mainY )
return RightSide;
else if( y1 > mainY )
return LeftSide;
else
return Intersect;
}
}
if( y1 < mainY && y2 < mainY )
return RightSide;
else if( y1 > mainY && y2 > mainY )
return LeftSide;
else if( y1 == mainY && y2 < mainY )
return RightSide;
else if( y2 == mainY && y1 < mainY )
return RightSide;
else if( y1 == mainY && y2 > mainY )
return LeftSide;
else if( y2 == mainY && y1 > mainY )
return LeftSide;
else
return Intersect;
}
BOOL SplitLine( CLine *pMainLine, CLine *pToSplit, CLine **pNewLeft, CLine **pNewRight )
{
// Get the angle for pMainLine.
// Rotate both the Lines by pMainLine's angle.
// Parametrically clip pToSplit against the X axis.
Angle angMain;
Fixed x1, y1, x2, y2;
Fixed t, newX, newY;
CPoint *pNewPoint;
CLine *pNewLine;
// The side of pMainLine that pToSplit ends up on.
SideDir splitSide;
angMain = GetAngle( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
pMainLine->pPoint2->localX, pMainLine->pPoint2->localY );
angMain = (ANGLE_RES - angMain) & ANGLE_MASK;
// Rotate all of pToSplit's vertices *around* pMainLine's first Point.
RotatePointYOnly( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
angMain, pToSplit->pPoint1->localX, pToSplit->pPoint1->localY,
&y1 );
RotatePointYOnly( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
angMain, pToSplit->pPoint2->localX, pToSplit->pPoint2->localY,
&y2 );
// Test for the special case here, where pToSplit lies exactly on pMainLine.
// In this case, a completely different action is taken. This needs to be before
// you get t, because you'll get a divide by zero error if this isn't handled.
if( y1 == FIX(pMainLine->pPoint1->localY) && y2 == FIX(pMainLine->pPoint1->localY) )
{
++nExactIntersections;
pNewLine = new CLine;
pLines->Append( pNewLine );
memcpy( pNewLine, pToSplit, sizeof(CLine) );
// Switch their directions.
pNewLine->pPoint2 = pToSplit->pPoint1;
pNewLine->pPoint1 = pToSplit->pPoint2;
// TODO: You might need to assign the new Line to a different side...
// Make sure the Lines are on the right sides of the partition and give them
// their correct textures.
*pNewLeft = pNewLine;
*pNewRight = pToSplit;
pNewLine->wallColor = pToSplit->wallColor;
pNewLine->idRightTex = pToSplit->idLeftTex;
pNewLine->idLeftTex = BAD_TEXTURE_ID;
pToSplit->idLeftTex = BAD_TEXTURE_ID;
return TRUE;
}
// Find where they intersect the Y axis of pMainLine's pPoint1.
t = FDiv( (FIX(pMainLine->pPoint1->localY) - y1), (y2-y1) );
// Find out which side each new line will be on.
if( y1 <= FIX(pMainLine->pPoint1->localY) )
splitSide = RightSide;
else
splitSide = LeftSide;
// Now get where the new Point should be.
x1 = FIX(pToSplit->pPoint1->localX);
y1 = FIX(pToSplit->pPoint1->localY);
x2 = FIX(pToSplit->pPoint2->localX);
y2 = FIX(pToSplit->pPoint2->localY);
newX = x1 + FMul( t, (x2-x1) );
newY = y1 + FMul( t, (y2-y1) );
// Create the new Point and Line and fill in their stuff.
pNewPoint = new CPoint;
pPoints->Append(pNewPoint);
pNewLine = new CLine;
memset( pNewLine, 0, sizeof(CLine) );
pLines->Append(pNewLine);
pNewPoint->localX = (WORD)UNFIX(newX);
pNewPoint->localY = (WORD)UNFIX(newY);
pNewLine->pPoint1 = pNewPoint;
pNewLine->pPoint2 = pToSplit->pPoint2;
pToSplit->pPoint2 = pNewPoint;
pNewLine->wallColor = pToSplit->wallColor;
pNewLine->idLeftTex = pToSplit->idLeftTex;
pNewLine->idRightTex = pToSplit->idRightTex;
// Fill in the return information.
if( splitSide == LeftSide )
{
*pNewLeft = pToSplit;
*pNewRight = pNewLine;
}
else
{
*pNewLeft = pNewLine;
*pNewRight = pToSplit;
}
return TRUE;
}
Angle DirectionDiff( Angle compass1, Angle compass2, SideDir diffDir )
{
Angle translatedCompass2;
// Put compass1 at 0 and translate compass2 by that amount.
translatedCompass2 = (Angle)((compass2 - compass1) & ANGLE_MASK);
if( diffDir == LeftSide )
return translatedCompass2;
else
return (Angle)(ANGLE_RES - translatedCompass2);
}
BOOL PrecalculateData( CLineArray *pLineList )
{
WORD i;
CLine *pCurLine;
WORD lineLength;
for( i=0; i < pLineList->NumElements(); i++ )
{
pCurLine = pLineList->GetLine(i);
// Do the texture mapping placement
pCurLine->texOriginX = pCurLine->pPoint1->localX;
pCurLine->texOriginY = pCurLine->pPoint1->localY;
pCurLine->lineAngle = GetAngle( pCurLine->pPoint1->localX, pCurLine->pPoint1->localY, pCurLine->pPoint2->localX, pCurLine->pPoint2->localY );
pCurLine->SetTextureXLength( 64 );
// Fill in the coefficients of the Line's plane equation.
pCurLine->A = pCurLine->pPoint1->localY - pCurLine->pPoint2->localY;
pCurLine->B = pCurLine->pPoint2->localX - pCurLine->pPoint1->localX;
pCurLine->C = -((pCurLine->A * pCurLine->pPoint1->localX) + (pCurLine->B * pCurLine->pPoint1->localY));
// Normalize A, B, and C.
lineLength = sqrt( SQR(pCurLine->pPoint2->localX - pCurLine->pPoint1->localX) + SQR(pCurLine->pPoint2->localY - pCurLine->pPoint1->localY) );
if( lineLength == 0 )
lineLength = 1;
pCurLine->A = FIX(pCurLine->A) / lineLength;
pCurLine->B = FIX(pCurLine->B) / lineLength;
pCurLine->C = FIX(pCurLine->C) / lineLength;
}
return TRUE;
}
BOOL CheckTreeValidity()
{
WORD i, j;
CLine *pMain, *pTest;
for( i=0; i < pLines->NumElements(); i++ )
{
pMain = pLines->GetLine(i);
if( pMain->pLeft == NULL && pMain->pRight == NULL )
continue;
for( j=0; j < pLines->NumElements(); j++ )
{
if( i == j )
continue;
pTest = pLines->GetLine(j);
if( pMain->pLeft == pTest->pLeft )
if( pMain->pLeft != NULL )
return FALSE;
if( pMain->pRight == pTest->pRight )
if( pMain->pRight != NULL )
return FALSE;
if( pMain->pLeft == pTest->pRight )
if( pMain->pLeft != NULL )
return FALSE;
if( pMain->pRight == pTest->pLeft )
if( pMain->pRight != NULL )
return FALSE;
}
}
return TRUE;
}